原始题目:剑指 Offer 18. 删除链表的节点 (opens new window)
解题思路:
遍历链表,当碰到节点 满足 时,将 的前驱节点的 指针指向 的后去节点, 。
代码:
public ListNode deleteNode(ListNode head, int val) {
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
while (head != null) {
if (head.val == val) {
pre.next = head.next;
break;
}
pre = head;
head = head.next;
}
return dummy.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
复杂度分析
- 时间复杂度: 为链表的节点数。最坏情况下,删除的节点在尾部,则需要遍历所有的节点。
- 空间复杂度: 占用常数大小的额外空间。